蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Pascal's Triangle Pascal's Triangle II 杨辉三角 杨辉三角 II

发表于 更新于 分类于 阅读次数： Valine：

Pascal’s Triangle

题目大意

输出帕斯卡三角前N行
1

121
1331

解题思路

注意帕斯卡三角中，除了首尾，其他值为上一层的两个邻值的和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        ans = []
        for i in range(numRows):
            row = []
            for j in range(i+1):
                row.append(1)
            if i > 1:
                for x in range(i - 1):
                    row[x+1] = ans[i-1][x] + ans[i-1][x+1]
            print row
            ans.append(row)
        return ans

Pascal’s Triangle II

题目大意

只返回第n行

解题思路

同时注意与上题的下标起点不一样（rowIndex先加个1 = =）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        rowIndex += 1
        ans = []
        if rowIndex == 0:
            return []
        for i in range(rowIndex):
            this = []
            for j in range(i+1):
                this.append(1)
            if i > 1:
                for x in range(i - 1):
                    this[x+1] = ans[i-1][x] + ans[i-1][x+1]
            print this
            ans.append(this)
        
        return ans[rowIndex - 1]

总结

帕斯卡三角， 我自己一开始试着写了一个函数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_num(i, j):
    # 三种特例，左边右边最上面
    if i == j:
        return 1
    if i == 0:
        return 1
    if i > 0 and j == 0:
        return 1
    # 输入有误返回False
    if i < j:
        return False
    else:
        return get_num(i - 1, j - 1) + get_num(i - 1, j)

print(get_num(7, 2))